package com.wyp168.leetcode;

import com.wyp168.leetcode.listnode.ListNode;
import com.wyp168.leetcode.treenode.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @ClassName LowestCommonAncestorSolution
 * @Title TODO
 * @Description TODO
 * @Author wyp168
 * @Date 2022/10/21 19:56
 */
public class LowestCommonAncestorSolution {
    public static void main(String[] args) {
        LowestCommonAncestorSolution solution = new LowestCommonAncestorSolution();
        TreeNode a = new TreeNode(6);
        TreeNode b = new TreeNode(2);
        TreeNode bb = new TreeNode(8);
        TreeNode c = new TreeNode(0);
        TreeNode cc = new TreeNode(4);
        TreeNode ccc = new TreeNode(7);
        TreeNode cccc = new TreeNode(9);
        TreeNode d = new TreeNode(3);
        TreeNode dd = new TreeNode(5);
        cc.left = d;
        cc.right = dd;
        b.left = c;
        b.right = cc;
        bb.left = ccc;
        bb.right = cccc;
        a.left = b;
        a.right = bb;

        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(8);
        System.out.println(solution.lowestCommonAncestor(a, p, q).val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pDepth = new ArrayList<>();
        List<TreeNode> qDepth = new ArrayList<>();
        TreeNode rootTemp1 = root;
        getDepth(rootTemp1, p, pDepth);
        TreeNode rootTemp2 = root;
        getDepth(rootTemp2, q, qDepth);
        TreeNode answer = null;
        for (int i = 0; i < pDepth.size() && i < qDepth.size(); i++) {
            if (pDepth.get(i) == qDepth.get(i)) {
                answer = pDepth.get(i);
            } else {
                break;
            }
        }
        return answer;
    }

    public void getDepth(TreeNode root, TreeNode targetNode, List<TreeNode> depthList) {
        if (root.val > targetNode.val) {
            depthList.add(root);
            //因为是二叉搜索树，如果比当前节点大，那就遍历左子树，否则相反
            getDepth(root.left, targetNode, depthList);
        } else if (root.val < targetNode.val) {
            depthList.add(root);
            getDepth(root.right, targetNode, depthList);
        } else {
            depthList.add(root);
        }

    }
}
